package strings;

/**
 * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
 * <p>
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * <p>
 * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
 * <p>
 * 说明：
 * <p>
 * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格；
 * 翻转后单词间应当仅用一个空格分隔；
 * 翻转后的字符串中不应包含额外的空格。
 */
public class N151_ReverseWords {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEveryWord(sb);
        return sb.toString();
    }

    private void reverseEveryWord(StringBuilder sb) {
        int left = 0, right = 1;
        int n = sb.length();
        while (right < n) {
            while (right < n && sb.charAt(right) != ' ') right++;
            reverseString(sb, left, right - 1);
            left = right + 1;
            right = left + 1;
        }
    }


    /**
     * 根据区间反转字符串
     */
    private void reverseString(StringBuilder sb, int left, int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, temp);
            left++;
            right--;
        }
    }

    /**
     * 去除字符串首位和中间多余的空格
     */
    private StringBuilder removeSpace(String s) {
        StringBuilder sb = new StringBuilder();
        int left = 0, right = s.length() - 1;
        while (s.charAt(left) == ' ') left++;
        while (s.charAt(right) == ' ') right--;
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ')
                sb.append(c);
            left++;
        }
        return sb;
    }


    public static void main(String[] args) {
        N151_ReverseWords solution = new N151_ReverseWords();
        System.out.println(solution.reverseWords(" the sky  is blue "));
    }
}
